const arr = [7, 12, 13, 15, 8, 10, 11, 12];

const lengthOfLIS = function (nums) {
  if (nums.length === 0) return 0;

  const tails = [nums[0]];

  for (let i = 0; i < nums.length; i++) {
    // 当遍历的数字大于纪录最后一项末尾数字时，新增；
    // 找到纪录中，第一个末尾大于该数字的纪录，更改其末尾；
    if (nums[i] > tails[tails.length - 1]) {
      tails.push(nums[i]);
    } else {
      const index = getFirstCreaterIndex(nums[i]);
      tails[index] = nums[i];
    }
  }

  function getFirstCreaterIndex(target) {
    for (let i = 0; i < tails.length; i++) {
      if (tails[i] >= target) {
        return i;
      }
    }
  }
  console.log(tails);
};

lengthOfLIS(arr);
